//
// Created by Administrator on 2021/9/19.
//
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

class Solution {
public:
    int minSteps(int n) {
        vector<int> dp(n + 1, 0);
        for (int i = 2; i <= n; ++i) {
            dp[i] = INT_MAX;
            for (int j = 1; j * j <= i; ++j) {
                if (i % j == 0) {
                    dp[i] = min(dp[i], dp[j] + i / j);
                    dp[i] = min(dp[i], dp[i / j] + j);
                }
            }
        }
        return dp[n];
    }
};

int main() {
    Solution solution;
    cout << solution.minSteps(3) << endl;
    return 0;
}